﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._20
{
    public class Leetcode15
    {
        public void Test()
        {
            try
            {
                var a = ThreeSum(new int[] { -2, 0, 1, 1, 2});
                ThreeSum(new int[] {0, -4, -1, -4, -2, -3, 2});

            }
            catch (Exception ex)
            { }
        }

        /*
         15. 3Sum

        Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

         */
        public IList<IList<int>> ThreeSum(int[] nums)
        {
            List<List<int>> listListInt = new List<List<int>>();
            List<int> listNums = new List<int>(nums);
            listNums.Sort();
            int tempInt = 0;
            bool lastHasOutput = false;
            for (int a = 0; a < listNums.Count - 2; a++)
            {
                if (lastHasOutput&&a > 0 && listNums[a] == listNums[a - 1])
                    continue;
                lastHasOutput = false;
                for (int b = a + 1; b < listNums.Count - 1; b++)
                {
                    tempInt = listNums[a] + listNums[b];
                    if (b > a + 1 && tempInt == listNums[a] + listNums[b - 1])
                        continue;
                    if (tempInt > 0)
                        continue;
                    if (tempInt + listNums[listNums.Count - 1] < 0)
                        continue;
                    for (int c = b + 1; c < listNums.Count; c++)
                    {
                        if (tempInt + listNums[c] == 0)
                        {
                            List<int> listTemp = new List<int>();
                            listTemp.Add(listNums[a]);
                            listTemp.Add(listNums[b]);
                            listTemp.Add(listNums[c]);
                            lastHasOutput = true;
                            listListInt.Add(listTemp);
                            break;
                        }
                    }

                }
            }
            return listListInt.ToArray();
        }

        /// <summary>
        /// 效率低
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public IList<IList<int>> ThreeSum2(int[] nums)
        {
            List<List<int>> listListInt = new List<List<int>>();
        
            List<string> listString = new List<string>();
            List<int> listNums = new List<int>();
            string strTemp = "";
            for (int i = 0; i < nums.Length; i++)
            {
                if (!listNums.Contains(nums[i]))
                    listNums.Add(nums[i]);
                else
                    continue;

                for (int j = i + 1; j < nums.Length; j++)
                {
                    for (int index = j + 1; index < nums.Length; index++)
                    {
                        if (nums[index] + nums[i] + nums[j] == 0)
                        {
                            List<int> list = new List<int>();
                            list.Add(nums[i]);
                            list.Add(nums[j]);
                            list.Add(nums[index]);
                            list.Sort();
                            strTemp = list[0].ToString() + "_" + list[1].ToString() + "_" + list[2].ToString();
                            if (!listString.Contains(strTemp))
                            {
                                listString.Add(strTemp);
                                listListInt.Add(list);
                            }
                            break;
                        }
                    }
                }
            }
            return listListInt.ToArray();
        }
    }
}
